package com.qch.edu.Tree.DiguiTaolu;

/**
 * @Author qch
 * @Date 2021/3/13
 * 题目：给定以课二叉树的头节点head（X）,返回这颗二叉树一个节点到另一个节点的最大举例
 * 1）与X无关 选择左树最大距离和右树最大距离中最大的距离
 * 2）与X有关 左树高度+1+右树高度
 *
 * 对左树要求 返回最大距离和你 的高度
 *
 * * 以X为头的节点
 *  * 潜在信息：左子树信息和右子树信息可以得到
 *
 *
 */
public class FastDistance {
    public static class Node {
        private int value;        //节点的值
        private Node node;        //此节点，数据类型为Node
        private Node left;        //此节点的左子节点，数据类型为Node
        private Node right;       //此节点的右子节点，数据类型为Node
        public Node(int data){
            this.value=data;
        }
    }
    public static class Info{
        public int maxDistance;
        public int height;
        public Info(int m,int h){
            maxDistance=m;
            height=h;
        }
    }
    public static Info process(Node X){
        if (X==null)
        {
            return new Info(0,0);
        }
        Info leftInfo = process(X.left);
        Info rightInfo = process(X.right);
        int height=Math.max(leftInfo.height,rightInfo.height)+1;//左右树中最大高度+头节点1
        int maxDistance=Math.max(Math.max(leftInfo.maxDistance,rightInfo.maxDistance),leftInfo.height+rightInfo.height+1);
        return new Info(maxDistance,height);

    }

    public static int distance(Node head){
        return process(head).maxDistance;
    }
    public static void main(String[] args) {

    }
}
